package com.example.hashtable;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定由若干 0 和 1 组成的矩阵 matrix，从中选出任意数量的列并翻转其上的 每个 单元格。翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。
 *  回经过一些翻转后，行与行之间所有值都相等的最大行数。
 *
 *  示例 1：
 * 输入：[[0,1],[1,1]]
 * 输出：1
 * 解释：不进行翻转，有 1 行所有值都相等。
 *
 *  示例 2：
 * 输入：[[0,1],[1,0]]
 * 输出：2
 * 解释：翻转第一列的值之后，这两行都由相等的值组成。
 *
 *  示例 3：
 * 输入：[[0,0,0],[0,0,1],[1,1,0]]
 * 输出：2
 * 解释：翻转前两列的值之后，后两行由相等的值组成。
 */
public class Leetcode1072_MaxEqualRowsAfterFlips {
    public static void main(String[] args) {
        int[][] matrix = {
                {0,0,0},
                {0,0,1},
                {1,1,0}};

        System.out.println(new Solution().maxEqualRowsAfterFlips(matrix));
    }

    static class Solution {

        /**
         * 观察可知满足这种规则的数据满足两行完全相同或者完全相反 -- 完全相反则两行的数对应进行异或得到全1
         * 于是可以转化成求矩阵中相同或者相反行的最大值
         *
         * a ^ b = c  => a ^ c = b
         * 基于以上可以将相同和相反进行统一
         * 具体操作:
         * 判断每行第一个是否是 1
         *   是 1 则每位与 1 进行异或再拼接到字符串中
         *   是 0 则直接拼接
         *
         * @param matrix
         * @return
         */
        private int maxEqualRowsAfterFlips1(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
            int res = 0;
            Map<String, Integer> map = new HashMap<>(); // key: 每行经过处理(可能和 1...1 进行过异或)得到的字符串 value: 字符串的次数
            for (int i = 0; i < matrix.length; i++) {
                StringBuilder sb = new StringBuilder();
                if (matrix[i][0] == 1) { // 为了将相同和相反行的判断进行统一
                    for (int j = 0; j < matrix[0].length; j++) {
                        sb.append(matrix[i][j] ^ 1);
                    }
                } else {
                    for (int j = 0; j < matrix[0].length; j++) {
                        sb.append(matrix[i][j]);
                    }
                }
                String lineStr = sb.toString();
                int newVal = map.getOrDefault(lineStr, 0) + 1;
                res = Math.max(res, newVal);
                map.put(lineStr, newVal);
            }
            return res;
        }

        public int maxEqualRowsAfterFlips(int[][] matrix) {
            return maxEqualRowsAfterFlips1(matrix);
        }
    }
}
